def heapConstruct(a, i, length):
    temp = a[i - 1]
    j = 2 * i
    while j <= length:
        if j<length and a[j - 1] < a[j]:
            j += 1
        if temp > a[j - 1]:
            break
        a[i - 1] = a[j - 1]
        i = j
        j = j * 2
    a[i - 1] = temp
    return a


def max_heap2(a):
    # 将无序的数组变成最大堆;堆是一个完全二叉树的结构,根据完全二叉树的性质,这里使用数组来存放最大堆
    length = len(a)
    for i in range(length // 2, 0, -1):  # 这里的i就不是数组下标了;数组下标=i-1
        # 从下往上,从右往左
        a = heapConstruct(a, i, length)
    # 开始堆排序
    for i in range(length, 1, -1):
        temp = a[0]
        a[0] = a[i - 1]
        a[i - 1] = temp
        a = heapConstruct(a, 1, i - 1)
    return a


if __name__ == "__main__":
    a = [3, 8, 7, 9, 0, 3, 1, 2]
    # 输出初始的无序数组
    print(a)
    a = max_heap2(a)
    print(a)
